import java.util.ArrayList;
import java.util.List;

public class Solution68 {
    void addSpaces(StringBuilder stringBuilder,int nums){
        for (int i = 0; i < nums; i++) {
            stringBuilder.append(' ');
        }
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans=new ArrayList<>();
        int t=0;
        while (t<words.length) {
            ArrayList<String> arrayList=new ArrayList<>();
            int count=words[t].length();
            int total=words[t].length();
            arrayList.add(words[t]);
            t++;
            while (t < words.length && count + 1 + words[t].length() <= maxWidth){
                arrayList.add(words[t]);
                count=count+1+words[t].length();
                total=total+words[t].length();
                t++;
            }
            int size=arrayList.size();
            StringBuilder stringBuilder=new StringBuilder(arrayList.get(0));
            if (size==1){
                addSpaces(stringBuilder,maxWidth-arrayList.get(0).length());
            }else{
                int every=(maxWidth-total)/(size-1);
                int first=maxWidth-total-every*(size-1);
                for (int i = 1; i < size; i++) {
                    addSpaces(stringBuilder,every);
                    if (i<=first) {
                        addSpaces(stringBuilder, 1);
                    }
                    stringBuilder.append(arrayList.get(i));
                }
            }
            ans.add(new String(stringBuilder));
        }
        String last=ans.get(ans.size()-1);
        ans.remove(ans.size()-1);
        String[] strings=last.split(" ");
        StringBuilder stringBuilder=new StringBuilder(strings[0]);
        int num=strings[0].length();
        for (int i=1;i<strings.length;i++){
            if (strings[i].length()!=0){
                addSpaces(stringBuilder,1);
                stringBuilder.append(strings[i]);
                num=num+1+strings[i].length();
            }
        }
        addSpaces(stringBuilder,maxWidth-num);
        ans.add(new String(stringBuilder));
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution68().fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"},16));
    }
}
